#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b);
void _MergeSort(int* arr, int left, int right);
void MergeSort(int* arr, int n);
void Print(int* arr, int size);

void swap(int* a, int* b)
{
	int mid = *a;
	*a = *b;
	*b = mid;
}

void _MergeSort(int* arr, int left, int right, int* tep)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tep);
	_MergeSort(arr, mid + 1, right, tep);
	int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
			tep[index++] = arr[begin1++];
		else
			tep[index++] = arr[begin2++];
	}
	while (begin1 <= end1)
	{
		tep[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tep[index++] = arr[begin2++];
	}
	for (int i = left; i <= right; i++)
	{
		arr[i] = tep[i];
	}
}

void MergeSort(int* arr,int n)
{
	int* tep = (int*)malloc(n * sizeof(int));

	_MergeSort(arr, 0, n - 1, tep);

}

void Print(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 1,0,3,6,2,5,8,7,4,9 };
	Print(arr, 10);
	MergeSort(arr,10);
	Print(arr, 10);
	return 0;
}